package leetcode.editor.offer;

import java.util.*;

// 剑指 Offer 48. 最长不含重复字符的子字符串
// https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
class ZuiChangBuHanZhongFuZiFuDeZiZiFuChuanLcof {
    public static void main(String[] args) {
        Solution solution = new ZuiChangBuHanZhongFuZiFuDeZiZiFuChuanLcof().new Solution();
        // solution.lengthOfLongestSubstring("abcabcbb");
        solution.lengthOfLongestSubstring("au");
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    // https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solutions/210129/mian-shi-ti-48-zui-chang-bu-han-zhong-fu-zi-fu-d-9/
    class Solution {
        /*public int lengthOfLongestSubstring(String s) {
            if (s.length() == 0) return 0;
            // dp[j] 代表以字符 s[j]s[j] 为结尾的 “最长不重复子字符串” 的长度
            int[] dp = new int[s.length()];
            dp[0] = 1;
            int res = 1;
            Map<Character, Integer> map = new HashMap<>();

            map.put(s.charAt(0), 0);
            for (int i = 1; i < s.length(); i++) {
                // 没有就返回-1
                Integer index = map.getOrDefault(s.charAt(i), -1);
                map.put(s.charAt(i), i);
                if (dp[i - 1] < i - index) dp[i] = dp[i - 1] + 1;
                else dp[i] = i - index;
                res = Math.max(res, dp[i]);
            }

        return res;
    }*/

        // 优化空间复杂度
        /*public int lengthOfLongestSubstring(String s) {
            Map<Character, Integer> map = new HashMap<>();
            int res = 0;
            int tmp = 0;

            for (int i = 0; i < s.length(); i++) {
                // 没有就返回-1
                Integer index = map.getOrDefault(s.charAt(i), -1);
                map.put(s.charAt(i), i);
                tmp = tmp >= i - index ? i - index : tmp + 1;
                res = Math.max(res, tmp);
            }

            return res;
        }*/

        // 向左边线性遍历，避免使用了哈希表，节约了空间
        /*public int lengthOfLongestSubstring(String s) {
            int res = 0;
            int tmp = 0;

            int j = 0;
            for (int i = 1; i < s.length(); i++) {
                j = i - 1;
                while (s.charAt(j) == s.charAt(i)) j--;
                tmp = tmp < i - j ? tmp + 1 : i - j;
                res = Math.max(res , tmp);
            }

            return res;
        }*/

        // 双指针+哈希表
        /*public int lengthOfLongestSubstring(String s) {
            Map<Character, Integer> map = new HashMap<>();
            // i表示左指针，j表示右指针
            int i = -1, res = 0;

            for (int j = 0; j < s.length(); j++) {
                if (map.containsKey(s.charAt(j))) i = Math.max(i, map.get(s.charAt(j)));
                map.put(s.charAt(j), j);
                res = Math.max(res, j - i);
            }

            return res;
        }*/

        // 滑动窗口
        public int lengthOfLongestSubstring(String s) {
            if (s == null || s.length() == 0) return 0;
            int l = 0, r = 0;
            Set<Character> set = new HashSet<>();
            int ans = 1;
            for (; r < s.length(); r++) {
                char c = s.charAt(r);
                while (set.contains(c)) {
                    set.remove(s.charAt(l));
                    l++;
                }
                ans = Math.max(ans, r - l + 1);
                set.add(c);
            }

            return ans;
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}
